package gold.utils;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Created by fanzhenyu02 on 2020/9/15.
 */
public class BFSUtil {

    /**
     * 广度优先遍历的通用标准形式
     * 如下代码从start出发遍历N个节点
     * 标准动作：只要有元素入队，就visited，防止重复入队
     */

    public void BFS(int start, int N, int[][] nextArray) {
        boolean visited[] = new boolean[N];
        Deque<Integer> queue = new LinkedList<>();
        queue.offerLast(start);
        visited[start] = true; //一定要一开始就置为true，防止重复遍历

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curId = queue.pollFirst();
                for (int nextId : nextArray[curId]) {
                    if (!visited[nextId]) {
                        queue.offerLast(nextId);
                        visited[nextId] = true;//这里非常重要，只要进入队列就置为true，防止重复遍历
                    }
                }
            }
        }
    }

    /**
     * 广度优先遍历的错误形式
     * 如下代码从start出发遍历N个节点
     */

    public void BFS_Error(int start, int N, int[][] nextArray) {
        boolean visited[] = new boolean[N];
        Deque<Integer> queue = new LinkedList<>();
        queue.offerLast(start);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curId = queue.pollFirst();
                visited[curId] = true; //这里置为true有些晚了
                for (int nextId : nextArray[curId]) {
                    if (!visited[nextId]) {
                        queue.offerLast(nextId);
                        // visited[nextId] = true;//这里非常重要，只要进入队列就置为true，防止重复遍历
                        // 此处缺少了入队节点的防遍历逻辑，可能出现遍历cur的时候，cur的next重复入队的情况
                    }
                }
            }
        }
    }
}
